﻿//最小基因变化(medium): https://leetcode.cn/problems/minimum-genetic-mutation/description/
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        queue<string>  q;
        unordered_map<string,bool> hash;
        int step=0;
        for(auto& str:bank)
        {
            hash[str]=false;
        }
        q.push(startGene);
        while(!q.empty())
        {
            step++;
            int leverSize=q.size();
            while(leverSize--)
            {
                 string out=q.front();
            q.pop();
            //选入out每个字母变化的字符串，字符串要在hash中存在，hash还要为flase;
            string words="ACGT";
            for(int i=0;i<out.size();i++)  //tmp[i]的变化
            {
                for(int j=0;j<4;j++)
                {
                    string tmp=out;
                    tmp[i]=words[j];
                    if(hash.count(tmp)&&!hash[tmp])
                    {
                        q.push(tmp);
                        hash[tmp]=true;
                        if(tmp==endGene)  return step; 
                    }
                }
            }
            }
           
        }
        return -1;
    }
};

//单词接龙(hard): https://leetcode.cn/problems/word-ladder/description/
class Solution {
public:
    int ladderLength(string startGene, string endGene, vector<string>& bank) {
        queue<string>  q;
        unordered_map<string,bool> hash;
        int step=0;
        for(auto& str:bank)
        {
            hash[str]=false;
        }
        q.push(startGene);
        while(!q.empty())
        {
            step++;
            int leverSize=q.size();
            while(leverSize--)
            {
                 string out=q.front();
            q.pop();
            //选入out每个字母变化的字符串，字符串要在hash中存在，hash还要为flase;
            string words(26,0);
            for(int i=0;i<26;i++)
            {
                words[i]='a'+i;
            }
            for(int i=0;i<out.size();i++)  //tmp[i]的变化
            {
                for(int j=0;j<26;j++)
                {
                    string tmp=out;
                    tmp[i]=words[j];
                    if(hash.count(tmp)&&!hash[tmp])
                    {
                        q.push(tmp);
                        hash[tmp]=true;
                        if(tmp==endGene)  return step+1; 
                    }
                }
            }
            }
           
        }
        return 0;
    }
};